<!DOCTYPE html>
<html lang="en">
	<meta charset="UTF-8">
	<title>LCT无rev操作</title>
<pre>node son[nmax][2],fa[nmax];
int val[nmax],sum[nmax];
#define lson(x) (son[x][0])
#define rson(x) (son[x][1])
#define root(x) (lson(fa[x])!=x&&rson(fa[x])!=x)
#define side(x) (rson(fa[x])==x)
inline void pu(node x) {sum[x]=sum[lson(x)]+sum[rson(x)]+val[x];}
inline void rot(node x) {node y=fa[x],z=fa[y];bool d=side(x);if(!root(y))son[z][side(y)]=x;fa[x]=z;son[y][d]=son[x][!d];fa[son[x][!d]]=y;son[x][!d]=y;fa[y]=x;pu(y);pu(x);}
inline void spl(node x) {for(y=fa[x];!root(x);rot(x),y=fa[x])if(!root(y))rot(side(x)==side(y)?y:x);pu(x);}

inline void acc(node x) {for(node y=0;x;y=x,x=fa[x])spl(x),rson(x)=y;}
inline node fro(node x) {acc(x);spl(x);while(lson(x))x=lson(x);spl(x);return x;}
#undef root
#undef side</pre></html>